package 冒泡排序;

import java.util.Arrays;

public class 冒泡排序 {

	public static void main(String[] args) {
//		int[] arr = {5,3,4,2,1};
//		bubbleSort(arr);
//		System.out.println(Arrays.toString(arr));
		
		
		int[] longInt = new int[80000];
		for (int i = 0; i < longInt.length; i++) {
			longInt[i] = (int) (Math.random()*10000);
		}
		
		long star = System.currentTimeMillis();
		bubbleSort(longInt);
		long end = System.currentTimeMillis();
		System.out.println((end-star) + "毫秒");
		System.out.println((end-star)/1000 + "秒");//13s
	}
	
	/**
	 * 冒泡排序 O(n^2)
	 * 
	 * 优化，添加flag判断，如果这一趟没有交换，说明已经有序
	 * @param arr
	 */
	public static void bubbleSort(int[] arr){
		
		//一共排 n-1 趟
		//一趟排 n-1 == (n-1)-1次
		//交换变量
		int temp = 0;
		//标志是否判断
		boolean flag = false;
		for (int i = 0; i < arr.length -1; i++) {
			
			//重置flag标志
			flag = false;
			
			for(int j = 0; j < arr.length - 1 - i ; j++) {
				if(arr[j] > arr[j+1]) {
					//如果发生交换，修改标志
					flag = true;
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
//			System.out.println("第" + (i+1) + "趟");
//			System.out.println(Arrays.toString(arr));
			
			//false说明没有交换
			if(!flag) {
				break;
			}
		}
	}
}

